home *** CD-ROM | disk | FTP | other *** search
/ PC Media 7 / PC MEDIA CD07.iso / share / prog / cm / cmtbintr.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  3.6 KB  |  82 lines
  1. // CmTBinTr.h
  2. // -----------------------------------------------------------------
  3. // Compendium - C++ Container Class Library
  4. // Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
  5. // -----------------------------------------------------------------
  6. // Binary tree template definition.
  7. // -----------------------------------------------------------------
  8.  
  9. #ifndef _CMTBINTR_H
  10. #define _CMTBINTR_H
  11.  
  12. #include <cm/include/cmtqueue.h>
  13. #include <cm/include/cmtstack.h>
  14.  
  15. template <class T> class CmTBinaryTreeNode;     // Node class stub.
  16. template <class T> class CmTBinaryTreeIterator; // Iterator class stub.
  17.  
  18. template <class T> class CmTBinaryTree : public CmTContainer<T> {
  19. public:
  20.   CmTBinaryTree();                              // Default constructor.
  21.   CmTBinaryTree(const CmTBinaryTree<T>&);       // Copy constructor.
  22.  ~CmTBinaryTree();                              // Tree destructor.
  23.  
  24.   CmTBinaryTree<T>& operator=(const CmTBinaryTree<T>&);  // Assignment. 
  25.  
  26.   Bool     add        (const T&);               // Add item to tree.
  27.   Bool     remove     (const T&);               // Remove item from tree.
  28.   const T& lookup     (const T&) const;         // Find equal item in tree.
  29.   Bool     contains   (const T&) const;         // Is equal item in tree?
  30.   void     removeAll  ();                       // Remove all items.
  31.   unsigned occurrences(const T&) const;         // Count occurrences of item.
  32.   const T& root       () const;                 // Return root tree item.
  33.   void     balance    ();                       // Balance the tree.
  34.  
  35.   CmTIterator<T>* newIterator() const;          // Get tree iterator.
  36.  
  37. protected:
  38.   void balanceHalf(CmTQueue<CmTBinaryTreeNode<T>*>*, int, int); // Balance.
  39.   static void killNode(CmTBinaryTreeNode<T>*);  // Destroy node children.
  40.  
  41.   CmTBinaryTreeNode<T> *_root;                  // Tree root node.
  42.   friend CmTBinaryTreeIterator<T>;              // Iterator can access.
  43. };
  44.  
  45. template <class T> class CmTBinaryTreeIterator : public CmTIterator<T> {
  46. public:
  47.   CmTBinaryTreeIterator(const CmTBinaryTree<T>&); // Iterator constructor.
  48.  ~CmTBinaryTreeIterator();                        // Iterator destructor.
  49.  
  50.   Bool     done    () const;                    // Check if end of container.
  51.   const T& next    ();                          // Advance and return.
  52.   const T& previous();                          // Return and backup.
  53.   const T& current () const;                    // Return current object.
  54.   void     first   ();                          // Move to first item.
  55.   void     last    ();                          // Move to last item.
  56.  
  57. protected:
  58.   const CmTBinaryTree<T>          &_tree;       // Tree being iterated.
  59.   CmTBinaryTreeNode<T>            *_node;       // Current tree node.
  60.   CmTStack<CmTBinaryTreeNode<T>*> *_stack;      // Node stack.
  61.   friend CmTBinaryTree<T>;                      // Tree class can access.
  62. };
  63.  
  64. template <class T> class CmTBinaryTreeNode {    // Node definition.
  65. protected:
  66.   CmTBinaryTreeNode<T> *_left;                  // Left node from this.
  67.   T                     _data;                  // Node key (data).
  68.   CmTBinaryTreeNode<T> *_right;                 // Right node from this.
  69.  
  70.   friend CmTBinaryTree<T>;                      // Tree class can access.
  71.   friend CmTBinaryTreeIterator<T>;              // Iterator can access.
  72.  
  73.   CmTBinaryTreeNode(const T& D)                 // Node constructor.
  74.                     : _left(NULL), _data(D), _right(NULL) {}
  75. };
  76.  
  77. #if defined(__TURBOC__) || defined(__xlC__)
  78. #include <cm/include/cmtbintr.cc>
  79. #endif
  80.  
  81. #endif
  82.